package com.code;

public class Gcd {


    /**
     * 求a，b的最大公约数gcd(a,b)
     * 辗转相除法（也叫欧几里得算法）gcd(a,b)=gcd(b,a%b)
     * 比如求27和15的最大公约数
     * 第一步 27%15 = 12
     * 第二步 15%12 = 3
     * 第三步 12%3 = 0
     * 得最大公约数为3
     */
    public static int gcdRecursion(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcdRecursion(b, a % b);
    }


    /**
     * 扩展欧几里得算法求逆元
     * ax+by=gcd(a,b)，其中gcd(a,b)代表a，b的最大公约数
     * 在辗转相除计算a和b求最大公约数对过程中，每一步的a和b的最大公约数都是相同的
     * 第一步中，设x，y的一组解为x1，y1，可得 ax1+by1=gcd(a,b)
     * 第二步中，设x，y的一组解为x2，y2，可得 bx2+(a%b)y2=gcd(a,b)
     * 上述两个式子对等 ax1+by1 = bx2+(a%b)y2
     * 假设 a=kb+a%b，实际 k就是a/b（整除）
     * 可得 ax1+by1 = bx2+(a-kb)y2
     * 化简 ax1+by1 = bx2 + ay2 - kby2
     * 化简 ax1+by1 = ay2 + b(x2-ky2)
     * 可得 x1 = y2 , y1 = x2-ky2 而 k=a/b（整除），所以 y1 = x2 - (a/b)y2
     * 而在最后一步中， b为0，a=gcd(a,b)所以x=1，而b=0，y是多少都可以成立，就假设y=0(y=0可得最小整数解，也可以领y为其他值成立)，这也是递归终止条件
     *
     * @return xy[0]为x，xy[1]为y
     */
    public static int[] exGcdRecursion(int a, int b) {
        if (b == 0) {
            return new int[]{1, 0};
        }
        int[] xy = exGcdRecursion(b, a % b);

        int x = xy[1];
        int y = xy[0] - a / b * xy[1];

        xy[0] = x;
        xy[1] = y;

        return xy;
    }


    /**
     * 扩展欧几里得算法
     * ax+by=gcd(a,b)求x，y的一组x为正的解
     * a(x1+b)+b(y1-a) = ax1 + ab + by1 -ab = ax1 + by1
     * 所以 x2 = x1+b，y2=y1-a 也能令原式成立
     *
     * @return xy[0]为x，xy[1]为y
     */
    public static int[] exGcd(int a, int b) {
        int[] xy = exGcdRecursion(a, b);
        while (xy[0] < 0) {
            xy[0] = b + xy[0];
            xy[1] = xy[1] - a;
        }
        return xy;
    }


}
